package com.dyz.leetcode._18_backtracking;

import java.util.*;

public class _77_combine {

    public List<List<Integer>> combine(int n, int k) {
        int [] nums = new int[n];
        for(int i=1; i<=n;i++){
            nums[i-1] = i;
        }
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[n];
        dfs(nums, 0, path, res,visited, k);
        return res;

    }

    private void dfs(int[] nums,
                     int index,
                     List<Integer> path,
                     List<List<Integer>> res,
                     boolean[] visited,
                     int k){

        if(path.size()==k){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i=index; i<nums.length; i++){
            if(!visited[i]){
                path.add(nums[i]);
                visited[i] = true;
                dfs(nums, i, path, res, visited, k);
                path.remove(path.size()-1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        List a = new ArrayList<>();
        a.add("aa");
        a.add("bb");
        String astr = String.join(",",a);
        List<String> listString = Arrays.asList(astr.split("','"));

    }
}
